Digital data transmitted over communication channels with impairments such as noise, distortions, and fading is inevitably delivered to the user with some errors. A similar situation occurs when digital data is stored on devices such as magnetic or optical media or solid-state memories that contain imperfections. The rate at which errors occur, referred to as the bit-error rate (BER), is a very important design criterion for digital communication links and for data storage. The BER is usually defined to be the ratio of the number of bit errors introduced to the total number of bits. Usually the BER must be kept smaller than a given preassigned value, which depends on the application. Error correction techniques based on the addition of redundancy to the original message can be used to control the error rate.
FIG. 1 is a block diagram of a system (e.g., data communications or data storage) 10 that illustrates the concept. The encoder 12 receives information bits from a source of digital data (not shown) and introduces redundant bits based on an error correction code. The combination of the data bits and the redundancy bits (which for block codes is called a “codeword”) is transmitted over the channel 14. As described before, the channel 14 can represent a digital communication link (such as a microwave link or a coaxial cable) or a data storage system (such as a magnetic or optical disk drive). The system includes a sampler 16, which periodically samples the analog signal received over the channel 14, based on a clock signal received from a clock 17, to generate a digital sample of the received signal. The digital sample is provided to a decoder 18, which decodes the digital sample to, ideally, generate the exact data bit sequence provided to the encoder 12.
The amount of redundancy inserted by the code employed by the encoder is usually expressed in terms of the code rate R. This rate is the ratio of the number of information symbols (e.g., bits) l in a block to the total number of transmitted symbols n in the codeword. That is, n=l+number of redundant symbols. Or in other words, n>l, or equivalently, R=l/n<1.
The most obvious example of redundancy is the repetition of the bit in a message. This technique, however, is typically unpractical for obvious reasons. Accordingly, more efficient coding mechanisms for introducing redundancy have been developed. These include block codes and convolutional codes. With block codes, the encoder breaks the continuous sequence of information bits into l-bit sections or blocks, and then operates on these blocks independently according to the particular code used. In contrast, convolutional codes operate on the information sequence without breaking it up into independent blocks. Rather, the encoder processes the information continuously and associates each long (perhaps semi-infinite) information sequence with a code sequence containing more symbols.
Block codes are characterized by three parameters: the block length n, the information length l, and the minimum distance d. The minimum distance is a measure of the amount of difference between the two most similar codewords. Ideally, the minimum distance d is relatively large.
Conceptually, for block codes the encoder 12 of FIG. 1 operates by performing a matrix multiplication operation on the message word m, comprising the bits from the digital source to be transmitted. The message word m, which may be considered a 1×l matrix, where l is the number of bits in the message word m, multiplies a l×n generator matrix G, where n>l, to generate the codeword c, a 1×n matrix. Because matrix multiplication is sometimes a computationally intensive process, in practice other, less computationally intensive schemes that generate the same matrix multiplication product are sometimes used. As used herein, references to “matrix multiplication” (or just “multiplication”) refer to any operation intended to produce the conceptual result of matrix multiplication, unless otherwise noted.
There are several known techniques for generating the generator matrix G. These include Hamming codes, BCH codes and Reed-Solomon codes. Another known code is a low density parity check (LDPC) code, developed by Gallager in the early 1960's. With block codes, a parity check matrix H of size (n−l)×n exists such that the transpose of H (i.e., HT), when multiplied by G, produces a null set; that is: G×HT=0. The decoder multiplies the received codeword c (m×G=c) by the transpose of H, i.e., c×HT. The result, often referred to as the “syndrome,” is a 1×(n−k) matrix of all 0's if c is a valid codeword.
For LDPC codes, the parity check matrix H has very few 1's in the matrix. The term “column weight,” often denoted as j, refers to the number of 1's in a column of H, whereas the term “row weight,” denoted as k, refers to the number of 1's in a row. An LDPC code can be represented by a bipartite graph, called a Tanner graph, that has as many branches as the number of non-zero elements in the parity check matrix. Gallager showed that with a column weight j≧3, which means three or more 1's in each column of matrix H, the minimum distance d increases linearly with n for a given column weight j and row weight k, and that the minimum distance d for a column weight of j=2 can increase at most logarithmically with the block length.
For data storage applications, the corrected bit-error rate (BER) (i.e., BER after error correction) is preferably on the order of 10−12 to 10−15. Possible bit errors can be introduced in data storage applications because of mistracking, the fly-height variation of the read head relative to the recording medium, the high bit density, and the low signal-to-noise ratio (SNR). Today, the goal of data storage applications is to realize storage densities of 1 Tbit/in2 and higher. Such a high bit density generates greater intersymbol interference (ISI), which complicates the task of realizing such low BERs. Further, with such high bit densities, the physical space each bit takes up on the recording medium becomes increasingly smaller, resulting in low signal strengths, thereby decreasing the SNR. In addition, computationally complex encoding schemes make the associated decoding operation computationally complex, making it difficult for the decoder for such a scheme to keep up with desired high data rates (such as 1 Gbit/s).
Accordingly, there exists a need for a code that can lead to corrected BERs of 10−12 to 10−15 despite the complications of large ISI and low SNR associated with going to higher bit densities, such as 1 Tbit/in2. Further, there exists a need for such a coding scheme to permit encoding and decoding at high data rates.